/**
 * 三数求和问题
 *
 * 真题描述：
 * 给你一个包含 n 个整数的数组 nums，
 * 判断 nums 中是否存在三个元素 a，b，c ，
 * 使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。
 * 注意：答案中不可以包含重复的三元组。
 *
 * 示例：
 * 给定数组 nums = [-1, 0, 1, 2, -1, -4]，
 * 满足要求的三元组集合为：[[-1, 0, 1], [-1, -1, 2]]
 *
 */

const threeNumsSum = (nums: Array<number>): Array<Array<number>> => {
	let res: Array<Array<number>> = []

	nums.sort((a, b) => a - b)

	let len = nums.length

	for (let i = 0; i < len - 2; i++) {
		let left = i + 1,
			right = len - 1

		if (i > 0 && nums[i] === nums[i - 1]) {
			continue
		}

		while (left < right) {
			if (nums[i] + nums[left] + nums[right] > 0) {
				right--
				while (left < right && nums[right] === nums[right + 1]) {
					right--
				}
			} else if (nums[i] + nums[left] + nums[right] < 0) {
				left++
				while (left < right && nums[left] === nums[left - 1]) {
					left++
				}
			} else {
				res.push([nums[i], nums[left], nums[right]])
				left++
				right--
				while (left < right && nums[right] === nums[right + 1]) {
					right--
				}
				while (left < right && nums[left] === nums[left - 1]) {
					left++
				}
			}
		}
	}

	return res
}

// 双指针法中的“对撞指针”法

// 在上面这道题中，左右指针一起从两边往中间位置相互迫近，这样的特殊双指针形态，被称为“对撞指针”。

// 什么时候你需要联想到对撞指针？
// 这里我给大家两个关键字——“有序”和“数组”。
// 没错，见到这两个关键字，立刻把双指针法调度进你的大脑内存。普通双指针走不通，立刻想对撞指针！

// 即便数组题目中并没有直接给出“有序”这个关键条件，我们在发觉普通思路走不下去的时候，也应该及时地尝试手动对其进行排序试试看有没有新的切入点——没有条件，创造条件也要上。

// 对撞指针可以帮助我们缩小问题的范围，这一点在“三数求和”问题中体现得淋漓尽致：因为数组有序，所以我们可以用两个指针“画地为牢”圈出一个范围，这个范围以外的值不是太大就是太小、直接被排除在我们的判断逻辑之外，这样我们就可以把时间花在真正有意义的计算和对比上。如此一来，不仅节省了计算的时间，更降低了问题本身的复杂度，我们做题的速度也会大大加快。
